/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-08
 * Time: 10:48
 */

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
//public class Solution {
//    public ListNode FindKthToTail(ListNode head,int k) {
//        if(k<=0){
//            return null;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        //先让fast走k步
//        while(fast!=null&&k-1!=0){
//            fast = fast.next;
//            k--;
//        }
//        while(fast!=null&&fast.next!=null){
//            fast = fast.next;
//            slow= slow.next;
//        }
//        return slow;
//    }
//}

//public class Solution {
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        //第一种方法让两个链表相同长度然后一起走
//        ListNode l1 = headA;
//        ListNode l2 = headB;
//        int cnt1 =0;
//        int cnt2 =0;
//        while(l1!=null){
//            ++cnt1;
//            l1=l1.next;
//        }
//        while(l2!=null){
//            ++cnt2;
//            l2 = l2.next;
//        }
//        ListNode long = headA;
//        ListNode short = headB;
//        int gap = cnt1-cnt2;
//        if(gap<0){
//            long = headB;
//            short = headA;
//        }
//        while(gap!=0){
//            long =long.next;
//            gap--;
//        }
//        //此时long和short在同一起跑线上
//        while(long!=null&&short!=null){
//            if(long!=null&&short!=null&&long ==short){
//                return long;
//            }
//            long = long.next;
//            short = short.next;
//        }
//        return null;
//    }
//}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode deleteDuplicates(ListNode head) {
//        if(head==null) {
//            return head;
//        }
//        //创建一个虚拟头结点  然后将不重复元素尾插到这个虚拟头结点上去
//        ListNode dummy = new ListNode(-1,null);
//        ListNode tmp =dummy;
//        ListNode cur = head;
//        while(cur!=null) {
//            if(cur.next!=null&&cur.val==cur.next.val) {
//                while(cur.next!=null&&cur.val==cur.next.val) {
//                    cur=cur.next;
//                }
//                cur =cur.next;
//            }else {
//                tmp.next =cur;
//                tmp = tmp.next;
//                cur =cur.next;
//            }
//        }
//        tmp.next=null;
//        return dummy.next;
//    }
//}


class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + arr[i];
        }
        int sum = 0;
        for (int start = 0; start < n; start++) {
            //0+1 0+2  0+3
            for (int length = 1; start + length <= n; length += 2) {
                int end = start + length - 1;//这里的end和start来控制区间长度
                sum += prefixSums[end + 1] - prefixSums[start];//计算区间之和
                //start 0
            }
        }
        return sum;
    }
}
public class TestDemo {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{1,4,2,5,3};
        solution.sumOddLengthSubarrays(arr);
    }

}
